package leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import javax.management.NotificationListener;

public class Solution3 {
	//校验括号
	public static boolean isValid(String s) {
		Stack stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '[' || s.charAt(i) == '{' || s.charAt(i) == '(') {
				stack.push(s.charAt(i));
			} else {
				if (stack.size() == 0) {
					return false;
				}
				char pop = (char) stack.pop();
				if (s.charAt(i) == '}' && pop == '{' || s.charAt(i) == ']' && pop == '['
						|| s.charAt(i) == ')' && pop == '(') {
					System.out.println("ok");
				} else {
					return false;
				}
			}
		}
		if (stack.size() == 0) {
			return true;
		} else {
			return false;
		}
	}

	public static int fib(int N) {
		if (N == 0)
			return 1;
		if (N == 1)
			return 1;
		return fib(N - 1) + fib(N - 2);
	}

	public static int fib2(int N) {
		if (N == 1)
			return 1;
		if (N == 2)
			return 2;
		int n1 = 1, n2 = 2;
		for (int i = 3; i <= N; i++) {
			int temp = n2;
			n2 = n1 + n2;
			n1 = temp;
		}
		return n2;

	}

	// 旋转数组 数组中的每一个元素向右移动K个位置
	public static void rotate(int[] nums, int k) {
		int temp = nums[0];
		for (int i = 1; i <= k; i++) {// 最外层控制移动的次数
			for (int j = 0; j < nums.length; j++) {
				// 数组中的每一个元素都往后挪一步
				if (j + 1 == nums.length) {// 移动最后一个元素
					nums[0] = temp;
				} else {
					int b = 0;
					b = temp;
					temp = nums[j + 1];
					nums[j + 1] = b;
				}

			}
		}
	}

	// 多数元素
	public static int majorityElement(int[] nums) {
		int result = 0;
		int bigcount = 0;
		for (int i = 0; i < nums.length; i++) {
			int count = 0;
			for (int j = i; j < nums.length; j++) {
				if (nums[i] == nums[j]) {
					count++;
				}
				// 如果不加停止判断 则时间太久失败
				if (count > nums.length / 2) {
					return nums[i];
				}
			}
			if (count > bigcount) {
				bigcount = count;
				result = nums[i];
			}
		}
		return result;
	}

	// excel 表列序号
	public static int titleToNumber(String s) {
		int result = 0;
		for (int i = 0; i < s.length(); i++) {
			char charAt = s.charAt(i);
			int number = 0;
			switch (charAt) {
			case 'A':
				number = 1;
				break;
			case 'B':
				number = 2;
				break;
			case 'C':
				number = 3;
				break;
			case 'D':
				number = 4;
				break;
			case 'E':
				number = 5;
				break;
			case 'F':
				number = 6;
				break;
			case 'G':
				number = 7;
				break;
			case 'H':
				number = 8;
				break;
			case 'I':
				number = 9;
				break;
			case 'J':
				number = 10;
				break;
			case 'K':
				number = 11;
				break;
			case 'L':
				number = 12;
				break;
			case 'M':
				number = 13;
				break;
			case 'N':
				number = 14;
				break;
			case 'O':
				number = 15;
				break;
			case 'P':
				number = 16;
				break;
			case 'Q':
				number = 17;
				break;
			case 'R':
				number = 18;
				break;
			case 'S':
				number = 19;
				break;
			case 'T':
				number = 20;
				break;
			case 'U':
				number = 21;
				break;
			case 'V':
				number = 22;
				break;
			case 'W':
				number = 23;
				break;
			case 'X':
				number = 24;
				break;
			case 'Y':
				number = 25;
				break;
			case 'Z':
				number = 26;
				break;
			default:
				break;
			}
			
			//每次递增的因子  两位的时候AA 1*26的一次方+1*26的零次方  AAA  1*26的2次 +1*26的一次方+1*26的0次方 
			int yinzi = (int) Math.pow(26, s.length() - i - 1);
			result += number * yinzi;
		}

		return result;
	}
	
	
	public static int titleToNumber2(String s) {
		int result = 0;
		for (int i = 0; i < s.length(); i++) {
			char charAt = s.charAt(i);
			//因为a-z是不间断的   z-a+1=26
			int number= charAt-'A'+1;
			
			//每次递增的因子  两位的时候AA 1*26的一次方+1*26的零次方  AAA  1*26的2次 +1*26的一次方+1*26的0次方 
			int yinzi = (int) Math.pow(26, s.length() - i - 1);
			result += number * yinzi;
		}

		return result;
	}
	
	 public static int strStr(String haystack, String needle) {
		 if(needle==null||"".equals(needle))//为空
			 return 0;
		 if(haystack==null||"".equals(haystack))//为空
			 return -1;
		//删除就成空串了
		 String temp=haystack.replaceAll(needle, "");
		 if("".equals(temp))
			 return 0;
		 if(haystack.indexOf(needle)<0)//不包含
			 return -1;
		 if(needle.length()<haystack.length()&&haystack.indexOf(needle)==0)//头部包含
			 return 1;
		 if(needle.length()>=haystack.length()&&haystack.indexOf(needle)==0)//全匹配
			 return 0;
		 int indexOf = haystack.indexOf(needle);
		 if(indexOf+needle.length()== haystack.length())//尾部包含
			 return 1;
		 
		 return 2;
	 }
	public static void main(String[] args) {
		// 有效的符号
		// String s ="[]()}";
		// System.out.println(isValid(s));

		// 爬楼梯 -- 斐波那契数列
		// System.out.println(fib2(44));

		// 移动数组位数
		// int[] nums = { 10, 1, 2, 3, 4, 5 };
		// rotate(nums, 8);
		// for (int i : nums) {
		// System.out.print(i + ",");
		// }

		// 多位元素
		int[] nums = { 2, 2, 1, 1, 1, 2, 2 };
		System.out.println(majorityElement(nums));

		System.out.println("zy--" + titleToNumber2("ZY"));
		System.out.println("AAA--" + titleToNumber2("AAA"));
		System.out.println("============================");
		System.out.println(strStr("aaa", "a"));
	}
}